package com.zjj.algorithm.learning.atguigu.sort;

import java.util.Arrays;

/**
 * 测试冒泡排序
 * * 算法描述
 * * 1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 * * 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 * * 3、针对所有的元素重复以上的步骤，除了最后一个；
 * * 4、重复步骤1~3，直到排序完成。
 * <p>
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定算法
 * 使用冒泡排序，排 80000 个数据，用时 9247 ms
 * 按照冒泡排序，若按照 小 -》 大 的顺序排，每一次都可以将一个大元素排到自己的位置
 *
 * @author zjj_admin
 * @date 2022/11/13 10:19
 */
public class BubbleSort {

    public static void main(String[] args) {

        int[] array = {3, 9, -1, 10, 20};
        bubbleSort(array);
        System.out.println("排序后的数据：" + Arrays.toString(array));

        //测试排 80000 个数据用时
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
        long time1 = System.currentTimeMillis();

        bubbleSort(arr);
        long time2 = System.currentTimeMillis();
        System.out.printf("使用冒泡排序，排 %d 个数据，用时 %s ms", arr.length, (time2 - time1));


    }

    private static void bubbleSort(int[] array) {
        //指定一个临时元素，用于交换两个元素的位置
        int temp = 0;
        //优化冒泡排序，指定当前循环有没有交换
        boolean flag = false;
        for (int i = 0; i < array.length - 1; i++) {

            // j < array.length - 1 - i ，每一次排序，都会有一个元素在后面自己的位置
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    flag = true;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }

//            System.out.printf("第 %d 趟排序后的结果：%s \n" , i + 1 , Arrays.toString(array));
            //当 flag 为false时，说明这一次循环没有交换，说明此时已经是有序的了，就可以退出循环了
            if (flag == false) {
                break;
            } else {
                //这里需要将 flag 变为false
                flag = false;
            }
        }
    }


}
